package com.heziguo.sortAlgorithm;

import com.heziguo.entity.Student;
import com.heziguo.utils.SortHelper;

import sun.tools.jar.resources.jar;

/**
 * 
 * @ClassName:  InsertSort 
 * @Package com.heziguo.sortAlgorithm    
 * @Description:插入排序 （首先考虑第一个元素 已经排序好了；再考虑第二个和第一个元素，比较；在考虑第三个 。。。）
 * @author: 贺子国 
 * @date:   2018年7月22日 下午11:05:37   
 *     
 * @Copyright: 2018 www.heziguo.com Inc. All rights reserved. 
 * 注意：
 */
public class InsertionSort {

	public static void main(String[] args) {
		/*Student[] student = {new Student("A",100),new Student("C",80),new Student("D",50),new Student("B",90)};
		InsertionSort.insertionSort(student);
		SortHelper.printArray(student);*/
		
		
		/*Integer [] arr = SortHelper.generateRandomArray(100, 0, 100);
		InsertionSort.insertionSort(arr);
		SortHelper.printArray(arr);*/
		
		
		try {
			Integer [] arr = SortHelper.generateRandomArray(100, 0, 100);
			SortHelper.sortTime(InsertionSort.class, "insertionSort", Comparable[].class, arr);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	 * @param <T>
	 * 
	 * @Title: insertionSort   
	 * @Description: 插入排序 (需要实现Comparable接口)   void
	 * @throws
	 */
	/*public static <T extends Comparable<? super T>> void insertionSort(T[] arr){
		//第一层循环查找当前需要考虑的位置
		for (int i = 1; i < arr.length; i++) {
			//第二层循环从当前考虑位置向前依次比较
			for (int j = i; j > 0 && arr[j].compareTo(arr[j-1]) > 0; j--) {
				T temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
			}
		}
	}*/
	
	/**
	 * @param <T>
	 * 
	 * @Title: insertionSort   
	 * @Description: 插入排序  改进版(需要实现Comparable接口)   void
	 * @throws
	 */
	public static <T extends Comparable<? super T>> void insertionSort(T[] arr){
		//第一层循环查找当前需要考虑的位置
		for (int i = 1; i < arr.length; i++) {
			T temp = arr[i];
			//第二层循环从当前考虑位置向前依次比较
			int j = i;
			for (; j > 0 && temp.compareTo(arr[j-1]) > 0; j-- ) {
				arr[j] = arr[j-1];
			}
			arr[j] = temp;
		}
	}
}
